Planning, in general, consists of computing a sequence of actions which, starting in an initial state or states, will achieve a set of goal states. Classical planning, then, is a constrained planning task, which is fully observable, deterministic, finite, static (i.e. the world does not change unless the agent acts), and discrete (i.e. time, actions, objects and effects are not continuous). Nonclassical planning, by contrast, is used to describe planning in partially observable or stochastic environments. 

% TODO: add appropriate subsection break here
\subsubsection{Difficulties of Classical Planning}

Typical problem-solving agents which make use of standard search algorithms (i.e. depth-first, breadth-first, $A^*$, etc) encounter several difficulties when solving classical planning problems; each of these must be kept in mind when designing a planning agent. First of all, the agent may be overwhelmed by ``irrelevant'' actions (that is, actions which do not necessarily bring the agent closer to achieving a goal). There are multiple ways within the classical planning community of discouraging a planning agent from considering irrelevant actions; the use of regression search, for example, is one way to attempt to handle this problem. 

Another difficulty in classical planning is finding a good heuristic function. Because a problem-solving agent would see the goal state only as a ``black box'' which is either true or false for a given state, it would require a new heuristic for each specific problem it encounters. A planning agent, however, may have access to a representation of the goal state as a conjunction of subgoals, in which case it can use a single domain-independent heuristic; namely, the number of unsatisfied conjuncts. 

Similarly, a problem-solving agent might be inefficient because of its inability to take advantage of problem decomposition. A planning agent which views a state as a conjunction of literals, however, might be able to decompose the goal into a conjunction of subgoals, and then attempt to find a plan to achieve each subgoal. There are tradeoffs to this approach, however. Even if a planning agent can work on subgoals independently, some additional work may be required to combine the resultant subplans. Additionally, for some domains, on one subgoal may undo another.

% TODO: add appropriate subsection break here
\subsubsection{Representing Classical Planning Problems}

Classical planning problems are represented using three formalisms: states, goals and actions. These constructs form the basis of the languages used to encode planning problems in such a way that planners can understand them and operate on them to search for plans. 

States in classical planning problems are represented by a conjunction of positive, ground, first-order propositional literals. Classical planning adopts the closed-world assumption, which states that any literals which are not explicitly enumerated as part of the state are false. This state representation may be manipulated by logical inference (when viewed as a conjunction of fluents), or with set operations (when viewed as a set of fluents).

% Actions are specified with respect to their preconditions and effects. The precondition of an action is a conjunction of positive literals which must be true in a state before the action can be executed. The effect of an action is a conjunction of literals which occur as a result of executing the action. For some literal $P$ in the effect, $P$ is asserted to be true in the resulting state; likewise, if $\lnot P$ is in the effect, $P$ is asserted to be false in the resulting state. It is worth noting that this action representation avoids the frame problem by leaving every literal not in an action's effect unchanged as a result of executing that action. 
% 
% A goal in a classical planning problem is a partially specified state, represented by a conjunction of ground literals. For some propositional state $s$, we say that $s$ satisfies a goal $g$ if all of the atoms in $g$ are in $s$ (where $s$ may also contain other atoms).

Actions may be represented by an action schema. This schema consists of the action name, a list of all variables used in the schema, a precondition, and an effect. Both the precondition and effect of the action are conjunctions of literals, which may be either positive or negative. The precondition gives a definition of states in which the action can be executed; the effect gives the result of executing the action. More formally, an action $a$ may be executed in some state $s$ if $s$ entails the precondition of $a$. If an action schema contains variables, there may be multiple states (ground instantiations of the variables in the action) which satisfy the preconditions of the action. 

The result of executing some action $a$ in state $s$ is given by state $s^\prime$. $s^\prime$ is first populated with the set of fluents in $s$, then all fluents which appear as negative literals in the effects of $a$ are removed, and finally the fluents which appear as positive literals in the effects of $a$ are added. 

A set of these action schemas gives the definition of a planning domain. A specific classical planning problem within such a domain is defined by adding an initial state and a goal. The initial state is a conjunction of ground atoms (where the closed-world assumption is assumed to hold). The goal is defined much like the precondition of an action; it is a conjunction of literals (either positive or negative) which may contain (existentially qualified) variables. A solution to a classical planning problem is a sequence of actions which begin with the initial state, and which entails the goal. 